package algorithm;

/**
 * 题目：
 *  一个矩阵只有0和1两种值，每个位置都可以和自己的上，下，左，右四个位置相连，如果有一片1连在一起，
 *  这个部分叫做一个岛，求一个矩阵中有多少个岛？
 *
 *  【举例】
 *   001010
 *   111010
 *   100100
 *   001000
 *   这个矩阵有3个岛
 *
 */
public class 岛问题 {

    public static void main(String[] args) {
        int[][] nums = new int[][]{{0,0,1,0,1,0},{1,1,1,0,1,0},{1,0,0,1,0,0},{0,0,1,0,0,0}};

        System.out.println(retuanIsland(nums));

    }

    public static int retuanIsland(int[][] nums){
        int m = nums.length;//高
        int n = nums[0].length;// 宽
        //循环

        int refect = 0;
        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ;j++){
                //递归渲染1为2；
                if(nums[i][j] == 1){
                    infect(nums, i , j , n, m);
                    refect ++;
                }
            }
        }
        return refect;
    }

    public static void infect(int[][] nums , int i , int j , int n , int m){
        //临界值
        if(i > m-1 || j > n-1 || i < 0 || j < 0 || nums[i][j] != 1 ){
            return;
        }

        nums[i][j] = 2;

        //上下左右遍历
        infect(nums,i-1,j , n , m);
        infect(nums,i+1,j , n , m);
        infect(nums,i,j-1 , n , m);
        infect(nums,i,j+1 , n , m);
    }


}
